package com.example.demo.leetcode.codetop.bytedance;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 *
 * 说明：每次只能向下或者向右移动一步。
 *
 *  
 *
 * 示例 1：
 *  1   3   1
 *  1   5   1
 *  4   2   1
 *
 * 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
 * 输出：7
 * 解释：因为路径 1→3→1→1→1 的总和最小。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-path-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/2/22 10:16
 */
public class 最小路径和 {

    private Integer res=Integer.MAX_VALUE;

    public int minPathSum(int[][] grid) {
        process(0,0,0,grid);
        return res;
    }

    public void process(int down,int right,int adder,int [][] grid){

        if(down>=grid.length || right>=grid[0].length){
            return;
        }
        if(down == grid.length-1 && right == grid[0].length-1){
            adder+=grid[down][right];
            res = Math.min(res,adder);
        }
        process(down+1,right,adder+grid[down][right],grid);
        process(down,right+1,adder+grid[down][right],grid);

    }


    /**
     * @Desciption:
     * 设置一个dp数组 dp中的值 都是最小路径值
     * 向下，向右的最小值直接通过累加可以得到
     * 那么dp值哪来的
     * 举例: 遍历到 i,j dp[i][j]= (grid[i][j]+dp[i-1][j])  / (grid[i][j]+dp[i][j-1]) 取最小值
     *
     * @param grid:
     */
    public int minPathSum2(int[][] grid) {
        int [][] dp = new int[grid.length][grid[0].length];

        dp[0][0] = grid[0][0];
        for(int i=1;i< dp.length;i++){
            dp[i][0] =dp[i-1][0] + grid[i][0];
        }
        for(int j=1;j<dp[0].length;j++){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }

        for(int i =1;i< dp.length;i++){
            for(int j=1;j<dp[0].length;j++){
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }

        return dp[dp.length-1][dp[0].length-1];
    }




}
